package LeetCode.Leet400_499.Leet470_479.Leet474;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/9/18 22:36
 * @Description TODO: 方法一   动态规划    17ms    99.51%
 */
class Solution_1 {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        // 初始化第一行和第一列均为0（默认为0，所以不需要任何代码）

        // 动态规划
        for(String s : strs){
            int zero_count = 0;
            int one_count = 0;
            // 计算1和0的个数
            for(char c : s.toCharArray()){
                if(c == '0'){
                    zero_count++;
                }else if(c == '1'){
                    one_count++;
                }
            }
            // 动态规划
            // 对于俩个容量分别为m和n的背包，s之前字符串数组的最大子集长度为dp[m][n]
            // 倒序遍历，是因为理论上应该使用三维数组dp来动态规划，这里为了节约空间减少了一维
            for(int i = m;i >= zero_count;i--){
                for(int j = n;j >= one_count;j--){
                    // 两种情况取较大值
                    // 1.放s，则子集数为1 + 剩余空间能放的最大子集数
                    // 2.不放s，则与上一次循环保持一致
                    dp[i][j] = Math.max(dp[i][j], dp[i - zero_count][j - one_count] + 1);
                }
            }

        }
        return dp[m][n];
    }
}
